package com.zdj.question;

/**
 * @author zdj
 * @date 2024-06-20 15:18
 * 从测试用例获取一个最大长度为19的数字字符串,问有多少个大于0的子序列构成的数字可以被3整除
 */
public class SubsequencesDivisibleByThree {

    public static void main(String[] args) {
        String numStr =args[0];
        int count = SubsequencesDivisibleByThreeSolution.countSubsequences(numStr);
        System.out.print(count);
    }
}

class SubsequencesDivisibleByThreeSolution{
    public static int countSubsequences(String numStr) {
        // 000 001 010 100 011 101 110 111
        int n = numStr.length();
        int count = 0;
        // 1 << n 代表 n个字符有多少种序列组合
        // 遍历i，就看二进制i的第j位是不是1， 如果是1则说明该序列是其中一种组合
        for (int i = 1; i < (1 << n); i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < n; j++) {
                System.out.println("i = " + toBinary(i) + " j = " + j + "   " + "1 << j = " + toBinary((1 << j)) + "   i & (1 << j) = " + (i & (1 << j)));
                // i的第j位是不是为1
                if ((i & (1 << j)) > 0) {
                    sb.append(numStr.charAt(j));
                    System.out.println("sb is " + sb);
                }
            }

            if (sb.length() > 0 && Long.parseLong(sb.toString()) % 3 == 0) {
                count++;
            }
        }

        return count;
    }

    public static String toBinary(int num) {
        // 使用StringBuilder来构建字符串，并初始化为"000"
        StringBuilder binary = new StringBuilder("000");

        // 从低位到高位填充二进制位，但只填充num不为0时的情况
        for (int i = 0; i < 3 && num > 0; i++) {
            // 从右往左替换字符
            binary.setCharAt(2 - i, (char) ('0' + num % 2));
            // 右移（除以2）以获取下一位
            num /= 2;
        }

        // 此时binary已经是3位的二进制字符串，无需额外处理
        return binary.toString();
    }
}
